
'''
给定一个已经排序好的列表 nums
以及一个整数 target

target 在 nums 里，就返回它的位置
如果不在，就返回它的插入位置
            vR=len(nums) - 1
1, 3, 4, 5 , 9
         ^L=mid+1
            ^mid

L = 4
R = 4
mid = 3

while L <= R:
    mid = (L + R) / 2
    if nums[mid] < target:
        # target 一定在 nums 的右半部分
        L = mid + 1
    else if nums[mid] > target:
        # target 一定在 nums 的左半部分
        R = mid - 1
    else:
        return mid # target 包含在 nums 里

# target 不在 nums 里
return L

target = 5 -> 3


6 -> 4

当我们看到 **排序列表**:
1. 折半查找
2. 左右位置
'''
def findPotentialPosition(nums: list[int], target: int) -> int:
    l = 0
    r = len(nums) - 1

    while l <= r:
        mid = (l + r) / 2

        if nums[mid] < target:
            # 如果中间位置小了
            l = mid + 1
        elif nums[mid] > target:
            # 如果中间位置大了
            r = mid - 1
        else: # 中间位置等于 target
            return mid
    
    # l > r 了，说明 target 不在 nums 里
    return l

# nums = [1, 5, 6, 10, 12] target = 8
# nums = [] target = 10
# nums = [6, 7, 8, 9] target = 9

'''
对于列表中间位置的理解
偶数个元素
1, 2, 3, 4
   ^mid
0        3

奇数个元素
1, 2, 3, 4, 5
      ^mid
0           4
'''